#include <bits/stdc++.h>

using namespace std;

int n, qq;

const int maxdot = 531441 + 5;
int t[maxdot];

int tmp[15];
int tmp2[15];
int q[maxdot];
int head,tail;
void Decode(int k)
{
    for (int i = 1; i <= n;i++)
    {
        tmp[i] = k % 3;
        k = k / 3;
    }
}

int Encode()
{
    int res = 0;
    int san = 1;
    for (int i = 1; i <= n;i++)
    {
        res = res + tmp[i] *san;
        san = san *3;
    }
    return res;
}

void PreBuild()
{
    head = 1; tail = 0;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n-i;j++)
        {
            int k = n - i - j;
            int now = 0;
            for (int t = 1; t<=i;t++)
            {
                tmp[++now] = 0;
            }
            for (int t = 1; t<=j;t++)
            {
                tmp[++now] = 1;
            }
            for (int t = 1; t<=k;t++)
            {
                tmp[++now] = 2;
            }
            int v = Encode();
            q[++tail] = v;
            t[v] = 1;
        }
    }
    while (head<=tail)
    {
        int now = q[head];
        Decode(now);
        for (int j = 1 ; j<= n; j++)
            tmp2[j] = tmp[j];
        for (int i =1 ; i<=n;i++)
        {
            for (int j = 1 ; j<= n; j++)
                tmp[j] = tmp2[j];
            for (int j = 1; j<= i/2 ;j++)
                swap(tmp[j],tmp[i-j+1]);
            int new_v= Encode();

            if (t[new_v] !=0) continue;
            q[++tail] = new_v;

            t[new_v] = t[now]+1;

        }
        head++;
    }
}

int main() {
  freopen("file.in","r",stdin);
  cin >> n >> qq;
  PreBuild();
  std::string st;
  for (int i = 1 ; i <= qq; i++)
  {
    cin >> st;
    int siz = st.size();
    for (int j = 0; j<siz;j++)
    {
        tmp[j+1]= st[j]-'A';
    }
    int now =Encode();

    std::cout << (t[now]-1) << std::endl;

  }
  return 0;
}
